/**
 * 汉诺塔问题
 *
 * 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开
 * 始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
 * (1) 每次只能移动一个盘子;
 * (2) 盘子只能从柱子顶端滑出移到下一根柱子;
 * (3) 盘子只能叠在比它大的盘子上。
 * 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
 * 你需要原地修改栈。
 *
 * 示例 1：
 *  输入：A = [2, 1, 0], B = [], C = []
 *  输出：C = [2, 1, 0]
 *
 * 示例 2：
 *  输入：A = [1, 0], B = [], C = []
 *  输出：C = [1, 0]
 *
 * 提示：
 * A 中盘子的数目不大于 14 个。
 */

import java.util.List;

/**
 * 典型的递归问题, 写一个函数作用是将 A 中的 size 个盘子 借助 B 移动到 C 上
 * 时间复杂度 : O(2 ^ n)
 * 空间复杂度 : O(n)
 */

public class Main {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }

    // 这里的意思是, 将 A 上的 size - 1 个盘子借助 C 移动到 B 上, 然后再将
    // A 上剩余的一个盘子 直接移动到 C 上, 最后, 将 B 上的 size - 1 个盘子
    // 借助 A 移动到 C 上, 这个函数的功能就是这样
    public void dfs (List<Integer> A, List<Integer> B, List<Integer> C, int size) {

        if (size == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }

        // 将 A 上的 size - 1 个盘子借助 C 移动到 B 上
        dfs(A, C, B, size - 1);

        // A 上剩余的一个盘子 直接移动到 C 上
        C.add(A.remove(A.size() - 1));

        // 将 B 上的 size - 1 个盘子借助 A 移动到 C 上
        dfs(B, A, C, size - 1);
    }
}